package alice.exercise.leetcode.difficult;

import java.util.*;
import java.util.function.ToIntFunction;
import java.util.stream.Stream;

/**
 * @author Alice
 * @since 2023-02-06 星期一 9:24
 */
class Solution {
  private static final int[] DUP_SUM_CACHE = new int[]{0, 0, 9, 261, 4725, 67509, 831429, 9287109, 97654149, 994388229};
  private static final int[] A9_CACHE = new int[]{1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880};

  public int A(int base, int n) {
    int sum = 1;
    for (int i = 0; i < n; i++) {
      sum *= (base - i);
    }
    return sum;
  }

  public int A9(int n) {
    return A(9, n);
  }

  // TODO 1012. 至少有 1 位重复的数字
  public int numDupDigitsAtMostN(int n) {
    if (n < 100) {
      return n / 11;
    }
    int bitCount = (int) Math.log10(n);
    // 39765
    int highest = (int) (n / Math.pow(10, bitCount));
    HashSet<Integer> set = new HashSet<>();
    set.add(highest);
    int curr = (highest - 1) * A9_CACHE[bitCount];
    int later = dupRes((int) (n - highest * Math.pow(10, bitCount)), set);
    return DUP_SUM_CACHE[bitCount] + n - curr - later - (int) Math.pow(10, bitCount) + 1;
  }

  private int dupRes(int n, Set<Integer> banned) {
    if (n == 0) {
      return 0;
    }
    int bitCount = (int) Math.log10(n);
    int highest = (int) (n / Math.pow(10, bitCount));
    banned.add(highest);
    int currP = 0;
    for (int i = 0; i < highest; i++) {
      if (banned.contains(i)) {
        continue;
      }
      currP++;
    }
    if (n < 10) {
      return currP + 1;
    }
    int next = (int) (n - highest * Math.pow(10, bitCount));
    return currP * A(10 - banned.size(), bitCount) + dupRes(next, banned);
  }

  public int numDupDigitsAtMostN1(int n) {
    int c = 0;
    for (int i = 1; i <= n; i++) {
      if (isDupDigitsAtMostN(i)) {
        c++;
      }
    }
    return c;
  }

  private boolean isDupDigitsAtMostN(int n) {
    int[] arr = new int[10];
    while (n > 0) {
      if (++arr[n % 10] > 1) {
        return true;
      }
      n /= 10;
    }
    return false;
  }

  // 2488. 统计中位数为 K 的子数组
  public int countSubarrays(int[] nums, int k) {
    int n = nums.length, index = 0;
    while (index < n && nums[index] != k) {
      index++;
    }
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, result = 0;
    for (int i = 0; i < n; i++) {
      sum += i == index ? 0 : (nums[i] > k ? 1 : -1);
      if (i < index) {
        map.put(sum, map.getOrDefault(sum, 0) + 1);
      } else {
        result += map.getOrDefault(sum, 0) + map.getOrDefault(sum - 1, 0);
      }
    }
    return result;
  }

  // 982. 按位与为零的三元组
  public int countTriplets1(int[] nums) {
    int maxVal = 1 << 16;
    int[] countArr = new int[maxVal];
    for (int n1 : nums) {
      for (int n2 : nums) {
        countArr[n1 & n2]++;
      }
    }
    int count = 0;
    for (int n : nums) {
      for (int i = 0; i < maxVal; i++) {
        if ((n & i) == 0) {
          count += countArr[i];
        }
      }
    }
    return count;
  }

  public int countTriplets(int[] nums) {
    int maxVal = 1 << 16;
    int[] countArr = new int[maxVal];
    for (int n1 : nums) {
      for (int n2 : nums) {
        countArr[n1 & n2]++;
      }
    }
    int count = 0;
    int mask = (1 << 16) - 1, x;
    for (int n : nums) {
      // 待遍历的数字中"1"出现的位置，只能是此时的n中的"0"出现的位置
      x = n ^ mask;
      while (true) {
        if ((n & x) == 0) {
          count += countArr[x];
        }
        if (x == 0) {
          break;
        }
        // 求"子集"的方法
        x = (x - 1) & mask;
      }
    }
    return count;
  }

  // TODO 1326. 灌溉花园的最少水龙头数目
  public int minTaps(int n, int[] ranges) {
    int[] range = new int[2];
    return -1;
  }

  // 1250. 检查「好数组」
  public boolean isGoodArray(int[] nums) {
    int len = nums.length;
    int k = nums[0];
    for (int i = 1; i < len; i++) {
      k = gcd(k, nums[i]);
    }
    return k == 1;
  }

  public int gcd1(int a, int b) {
    int min = Math.min(a, b);
    int max = Math.max(a, b);
    int over = max % min;
    if (over == 0) {
      new ArrayList<String>().toArray(new String[0]);
      return min;
    }
    return gcd(min, over);
  }

  public int gcd(int a, int b) {
    int min = Math.min(a, b);
    int max = Math.max(a, b);
    int over = max % min;
    while (over != 0) {
      max = min;
      min = over;
      over = max % min;
    }
    return min;
  }

  // 1223. 掷骰子模拟
  public int dieSimulator(int n, int[] rollMax) {
    int MOD = 1000000007;
    long total = (long) Math.pow(6, n);
    for (int max : rollMax) {
      if (max >= n) {
        continue;
      }
      for (int j = max + 1; j <= n; j++) {
        total -= overCount(n, j);
      }
    }
    return (int) (total % MOD);
  }

  public int overCount(int n, int m) {
    int diff = n - m;
    if (diff == 0) {
      return 1;
    }
    if (diff == 1) {
      return 10;
    }
    int totalTimes = n - m + 1;
    int minCountOf6 = diff - 2;
    return (int) ((Math.pow(6, minCountOf6) * 25) * Math.max(totalTimes - 2, 0) + (Math.pow(6, minCountOf6 + 1) * 5) * 2);
  }

  // 850. 矩形面积 II
  public int rectangleArea(int[][] rectangles) {
    int MOD = 0;
    Map<Integer, int[]> map = new HashMap<>();
    for (int[] rectangle : rectangles) {
      myCollect(map, rectangle);
    }
    return map.values().stream().mapToInt(new ToIntFunction<int[]>() {
      @Override
      public int applyAsInt(int[] value) {
        return (value[1] - value[0]) % MOD;
      }
    }).sum();
  }

  private void myCollect(Map<Integer, int[]> map, int[] arr) {
    int xMin = arr[0];
    int xMax = arr[2];
    Stream.iterate(arr[1] + 1, integer -> integer + 1).limit(arr[3] - arr[1]).parallel().forEach(i -> map.compute(i, (integer, ints) -> refresh(ints, xMin, xMax)));
  }

  private int[] refresh(int[] old, int min, int max) {
    if (old == null) {
      return new int[]{min, max};
    }
    old[0] = Math.min(old[0], min);
    old[1] = Math.max(old[1], max);
    return old;
  }
}
